# [BM22 比较版本号](https://www.nowcoder.com/practice/2b317e02f14247a49ffdbdba315459e7?tpId=295&tqId=40180&rp=1&difficulty=&judgeStatus=&tags=/question-ranking)
def compare1(self, version1: str, version2: str) -> int:
    len1, len2 = len(version1), len(version2)
    i, j = 0, 0

    while i < len1 or j < len2:
        num1, num2 = 0, 0  # 每次循环开始时，修订号初始化为0

        while i < len1 and version1[i] != '.':
            num1 = num1 * 10 + int(version1[i])
            i += 1

        while j < len2 and version2[j] != '.':
            num2 = num2 * 10 + int(version2[j])
            j += 1

        if num1 > num2:
            return 1
        elif num1 < num2:
            return -1

        (i, j) = (i + 1, j + 1)

    return 0

def compare2(self, version1: str, version2: str) -> int:
    # 将版本号按 '.' 分割成整数列表
    v1 = list(map(int, version1.split(".")))
    v2 = list(map(int, version2.split(".")))

    # 获取两个版本号列表的最大长度
    length = max(len(v1), len(v2))

    # 比较每个修订号
    for i in range(length):
        # 如果当前版本号修订号不足，补充为0
        v1_value = v1[i] if i < len(v1) else 0
        v2_value = v2[i] if i < len(v2) else 0

        # 比较修订号
        if v1_value > v2_value:
            return 1
        elif v1_value < v2_value:
            return -1

    # 如果所有修订号都相等
    return 0

# [BM20 数组中的逆序对](https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tqId=40178&rp=1&difficulty=&judgeStatus=&tags=/question-ranking)
from heapq import merge
from typing import List
class Solution:
    MOD = 1000000007

    def merge_count(self, nums: List[int], temp_nums: List[int], l: int, r: int) -> int:
        if l >= r:
            return 0

        mid = (l + r) // 2
        count = self.merge_count(nums, temp_nums, l, mid) + self.merge_count(nums, temp_nums, mid + 1, r)
        count += self.merge(nums, temp_nums, l, mid, r)

        return count % Solution.MOD

    def merge(
        self, nums: List[int], temp_nums: List[int], l: int, mid: int, r: int
    ) -> int:
        count = 0  # 初始化逆序对计数
        i, j, k = l, mid + 1, l  # k 应该从 l 开始，而不是从 0

        # 合并两个已排序的子数组
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                temp_nums[k] = nums[i]
                i += 1
            else:
                temp_nums[k] = nums[j]
                count += (mid - i + 1)  # 如果 nums[i] > nums[j]，则 nums[i] 到 nums[mid] 之间的所有元素都和 nums[j] 形成逆序对
                j += 1
            k += 1

        # 将左子数组剩余的元素加入temp_nums
        while i <= mid:
            temp_nums[k] = nums[i]
            i += 1
            k += 1

        # 将右子数组剩余的元素加入temp_nums
        while j <= r:
            temp_nums[k] = nums[j]
            j += 1
            k += 1

        # 将合并后的数据复制回原数组
        for i in range(l, r + 1):
            nums[i] = temp_nums[i]

        return count % Solution.MOD

    def InversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        temp_nums = [0] * n
        return self.merge_count(nums, temp_nums, 0, n - 1)

    # (1089. 复写零)https://leetcode.cn/problems/duplicate-zeros/submissions/635818930/
    def duplicateZeros(self, arr):
        """
        :type arr: List[int]
        :rtype: None Do not return anything, modify arr in-place instead.
        """
        if not arr:
            return arr

        dest = -1
        cur = 0
        n = len(arr)
        # 1. 找到复写的最后一位位置
        while dest < n - 1:
            if arr[cur] != 0:
                dest += 1
            else:
                dest += 2
            if dest >= n - 1:
                break
            cur += 1

        # 1.5 处理边界情况
        if dest == n:
            arr[n - 1] = 0
            dest -= 2
            cur -= 1

        # 2. 从后向前复写
        while cur >= 0:
            if arr[cur] != 0:
                arr[dest] = arr[cur]
                dest -= 1
            else:
                arr[dest] = 0
                dest -= 1
                arr[dest] = 0
                dest -= 1
            cur -= 1

        return arr

    # (283. 移动零)https://leetcode.cn/problems/move-zeroes/description/
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return

        dest = -1
        for cur in range(len(nums)):
            if nums[cur] != 0:
                dest += 1
                nums[cur], nums[dest] = nums[dest], nums[cur]


    # (202. 快乐数)[https://leetcode.cn/problems/happy-number/submissions/635940731/]
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """

        # 计算一个整数的每位平方和
        def bitSquare(num):
            sum = 0
            while num > 0:
                bit = num % 10
                sum += bit * bit
                num /= 10
            return sum

        # 快乐数成环：快慢指针
        slow = n
        fast = bitSquare(n)
        while slow != fast:
            slow = bitSquare(slow)
            fast = bitSquare(bitSquare(fast))

        return fast == 1  # 判断相遇位置

    # (11. 盛最多水的容器)[https://leetcode.cn/problems/container-with-most-water/description/]
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0; right = len(height) - 1
        max_v = 0
        while left < right:
            v = (right - left) * min(height[right], height[left]) # 计算容量
            max_v = max(v, max_v)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_v

    # (611. 有效三角形的个数)[https://leetcode.cn/problems/valid-triangle-number/submissions/635961522/]
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        n = len(nums);
        total = 0
        # i 固定最大边
        for i in range(n - 1, 1, -1):
            left = 0;
            right = i - 1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    total += (right - left)
                    right -= 1
                else:
                    left += 1
        return total

    # (LCR 179. 查找总价格为目标值的两个商品)[https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/]
    def twoSum(self, price, target):
        """
        :type price: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0;
        right = len(price) - 1
        while left < right:
            if price[left] + price[right] > target:
                right -= 1
            elif price[left] + price[right] < target:
                left += 1
            else:
                return [price[left], price[right]]

    # (15. 三数之和)[https://leetcode.cn/problems/3sum/submissions/636200679/]
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return nums

        nums.sort()

        n = len(nums)
        ret = []
        for i in range(n - 2):  # 固定一位数
            # 跳过重复的数
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1;
            right = n - 1
            while left < right:
                cur_sum = nums[i] + nums[left] + nums[right]
                if cur_sum > 0:
                    right -= 1
                elif cur_sum < 0:
                    left += 1
                else:  # 保存当前结果，并跳过重复项
                    ret.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1;
                    right -= 1

        return ret

    # (18. 四数之和)[https://leetcode.cn/problems/4sum/description/]
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not nums:
            return nums

        nums.sort()
        n = len(nums)
        ret = []
        # 两层for循环固定前两位
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:  # 去重
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:  # 去重
                    continue
                left = j + 1;
                right = n - 1
                while left < right:
                    cur_sum = nums[left] + nums[right] + nums[i] + nums[j]
                    if cur_sum > target:
                        right -= 1
                    elif cur_sum < target:
                        left += 1
                    else:
                        ret.append([nums[i], nums[j], nums[left], nums[right]])
                        # 去重
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1

                        left += 1;
                        right -= 1
        return ret